/* 
    打家劫舍3
    一颗二叉树，树上的每个点都有对应的权值，每个点有两种状态(选中和不选中)，问在
    不能同时选中父子关系的点的情况下，能选中的点的最大权值和是多少

    f(o) 表示选中 o 节点的情况下，o节点的子树上被选择的节点的最大权益值
        o的左右孩子不能被选中 
    g(o) 表示不选中 o 节点的情况下，o节点的子树上被选择的节点的最大权值和
        o的左右孩子咳哟被选中，也可以不被选中
        故它对o的贡献是x被选中和不被选中的情况下的较大值故:g(o) = max{f(l)g(l)} + max{f(r)g(r)}

*/
var rob = (root) => {
    // 选中 o  节点的最大贡献值
    const f = new Map()
    // 不选中 o 节点的最大贡献值
    const g = new Map()

    const dfs = () => {
        if (!node) return
        dfs(node.left)
        dfs(node.right)
        f.set(node, node.val + (g.get(node.left) || 0) + (g.get(node.right) || 0))
        g.set(node, Math.max(f.get(node.left) || 0), g.get(node.left) || 0) + Math.max(f.get(node.right) || 0, g.get(node.right) || 0)
    }
    dfs(root)
    return Math.max(f.get(node) || 0, g.get(node) || 0)
}
var rob = (root) => {
    const dfs = (node) => {
        if (!node) return [0, 0]
        const left = dfs(node.left)
        const right = dfs(node.right)
        const selected = node.val + left[1] + right[1]
        const notSelected = Math.max(...left) + Math.max(...right)
        return [selected, notSelected]
    }
    return Math.max(...dfs(root))
}